package club.xiaojiawei.greedy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Comparator;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/30/22 2:03 PM
 * @question 56. 合并区间
 * @description 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 */
public class Merge56 {

    public static void main(String[] args) {
        Merge56 test = new Merge56();
        int[][] result = test.merge3(new int[][]{ {1, 4}, {5, 6}});
        Arrays.stream(result).forEach(arr -> System.out.println(Arrays.toString(arr)));
    }

    /**
     * 排序+贪心
     * 时间复杂度O(logn)
     * 空间复杂度O(logn)
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(i -> i[0]));
        ArrayList<int[]> result = new ArrayList<>();
        int rearIndex = intervals[0][1];
        result.add(new int[]{intervals[0][0], intervals[0][1]});
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= rearIndex){
                int[] ints = result.get(result.size() - 1);
                rearIndex =ints[1] = Math.max(ints[1], intervals[i][1]);
            }else {
                result.add(new int[]{intervals[i][0], intervals[i][1]});
                rearIndex = intervals[i][1];
            }
        }
        return result.toArray(new int[result.size()][2]);
    }

    /**
     * 排序+贪心（优化）
     * 时间复杂度O(logn)
     * 空间复杂度O(1)
     * @param intervals
     * @return
     */
    public int[][] merge2(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(i -> i[0]));
        int index = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= intervals[index][1]){
                intervals[index][1] = Math.max(intervals[index][1], intervals[i][1]);
            }else {
                index++;
                intervals[index][0] = intervals[i][0];
                intervals[index][1] = intervals[i][1];
            }
        }
        return Arrays.copyOfRange(intervals, 0, index + 1);
    }

    /**
     * 民间-BitSet二进制（nb）
     * @param intervals
     * @return
     */
    public int[][] merge3(int[][] intervals) {
        BitSet bitSet = new BitSet();
        int max = 0;
        for (int[] interval : intervals) {
//            这里乘2的意义：因为题目要求是重叠的区间，所以{1, 4}, {5, 6}并不是重叠区间（但它们的二进制是连在一块的 1111110，会导致误判），如果乘2则得{2, 8}, {10, 12}（二进制为1110111111100），这样后面就不会把这两个区间当作重叠区间处理了
            int temp = (interval[1] << 1) + 1;
//            void set(int startIndex, int endIndex, boolean v)
//            将指定的 fromIndex（包括）到指定的 toIndex（不包括）范围内的位设置为指定的值。
            bitSet.set(interval[0] << 1, temp, true);
            max = Math.max(temp, max);
        }
        int index = 0, count = 0;
        while (index < max) {
//            int nextSetBit(int startIndex)
//            返回第一个设置为 true 的位的索引，这发生在指定的起始索引或之后的索引上。
            int start = bitSet.nextSetBit(index);
//            int nextClearBit(int startIndex)
//            返回第一个设置为 false 的位的索引，这发生在指定的起始索引或之后的索引上。
            int end = bitSet.nextClearBit(start);
            int[] item = {start >> 1, (end - 1) >> 1};
            intervals[count++] = item;
            index = end;
        }
        int[][] ret = new int[count][2];
        System.arraycopy(intervals, 0, ret, 0, count);
        return ret;
    }
}
